Stereo disparity estimation is one of the most active research areas in the field of three-dimensional or stereo vision. Stereo disparity is the spatial offset or displacement between two matching pixels, where one pixel is in a reference image, the other pixel is in a search image, and both pixels correspond to the same point in physical space. The reference and search images are the images viewed by the left and right eyes, respectively.
In order to determine the pixel in the search image which matches a given pixel in the reference image, the coordinates of the pixels in the two images must first be established. A similarity measure is then computed between pixels in a window of predetermined size centered at the given pixel in the reference image (i.e., the reference pixel) and pixels that are candidates to match the reference pixel in a window of the same size centered at each candidate pixel in the search image. The pixel in the search image that yields the greatest value of the similarity measure is considered to be the pixel that matches the reference pixel.
A disparity map for the reference image is obtained by computing the similarity measure between a reference pixel and each candidate matching pixel in a search range for every pixel in the reference image. Generation of the disparity map is greatly simplified by imposition of the “epipolar constraint” on the candidate matching pixels, whereby the candidate matching pixels are limited to those which lie on the same horizontal line as the reference pixel.
FIG. 1 illustrates matching subject to the epipolar constraint. To determine the pixel in the search image that most closely matches the starred reference pixel, the similarity measure is computed for a window centered at the reference pixel and a window in the search image centered at a candidate matching pixel as the window in the search image is moved along a horizontal line within a search range. The candidate search pixel that yields the greatest value of the similarity measure is considered to be the pixel that matches the reference pixel. The spatial displacement between the matching pixel from the reference pixel is the stereo disparity for the reference pixel.
Similarity measures typically used to determine matching pixels include the sum of squared differences (SSD), the sum of absolute differences (SAD), and the normalized cross correlation (NCC). For each of these similarity measures, the contribution of a given search pixel to the disparity map depends on the light intensity at the given search pixel. The disparity boundary between a region within which there are large variations in light intensity therefore tends to extend into any adjacent region within which there are small variations in light intensity. This phenomenon, known as “boundary overreach”, generates misleading disparity values near the boundary of an object.